<!DOCTYPE html>
<html>
  <head>
    <meta charset="utf-8"> <meta name="viewport" content="width=device-width">
    <title>k-median问题在Metric空间上的近似解法</title>
    <meta name="viewport" content="width=device-width,initial-scale=1, shrink-to-fit=no">
    <!-- Bootstrap CSS -->
    <link rel="stylesheet"
          href="https://cdn.jsdelivr.net/npm/bootstrap@4.5.0/dist/css/bootstrap.min.css"
          integrity="sha384-9aIt2nRpC12Uk9gS9baDl411NQApFmC26EwAOH8WgZl5MYYxFfc+NcPb1dKGj7Sk"
          crossorigin="anonymous">
    <link rel="stylesheet"
          href="//cdnjs.cloudflare.com/ajax/libs/highlight.js/10.5.0/styles/androidstudio.min.css">
<!--    <link rel="stylesheet" href="/web_template_css.css">-->
    <!-- this is highlight.js -->
    <script src="https://polyfill.io/v3/polyfill.min.js?features=es6"></script>
    <script id="MathJax-script" async
            src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js">
    </script>
    <script  src="https://cdn.jsdelivr.net/npm/jquery@3.5.1/dist/jquery.slim.min.js"
    integrity="sha384-DfXdz2htPH0lsSSs5nCTpuj/zy4C+OGpamoFVy38MVBnE+IbbVYUew+OrCXaRkfj" crossorigin="anonymous"></script>
    <script src="https://cdn.jsdelivr.net/npm/popper.js@1.16.0/dist/umd/popper.min.js"
    integrity="sha384-Q6E9RHvbIyZFJoft+2mJbHaEWldlvI9IOYy5n3zV9zzTtmI3UksdQRVvoxMfooAo" crossorigin="anonymous"></script>
    <script src="https://cdn.jsdelivr.net/npm/bootstrap@4.5.0/dist/js/bootstrap.min.js"
    integrity="sha384-OgVRvuATP1z7JjHLkuOU7Xw704+h835Lr+6QL9UvYjZE3Ipu6Tp75j7Bh/kR0JKI" crossorigin="anonymous"></script>
    <script src="//cdnjs.cloudflare.com/ajax/libs/highlight.js/10.5.0/highlight.min.js"></script>
    <style>
      img{
        display: block;
        height: auto;
        max-width: 100%;
      }
    </style>
  </head>
  <body>
    <nav class="navbar navbar-expand-lg navbar-light bg-light">
        <a class="navbar-brand" href="#">kvrmnks</a>
        <button class="navbar-toggler" type="button" data-toggle="collapse" data-target="#navbarNav" aria-controls="navbarNav" aria-expanded="false" aria-label="Toggle navigation">
          <span class="navbar-toggler-icon"></span>
        </button>
        <div class="collapse navbar-collapse" id="navbarNav">
          <ul class="navbar-nav">
            <li class="nav-item active">
              <a class="nav-link" href="./../../../../../index.html" target="_self">Home <span class="sr-only">(current)</span></a>
            </li>
            <li class="nav-item">
              <a class="nav-link" href="./../../../../../blog.html">Blog</a>
            </li>
            <li class="nav-item">
              <a class="nav-link" href="./../../../../../about.html">About</a>
            </li>
          </ul>
        </div>
      </nav>



    <div class='container'>
      <h2>k-median问题</h2>

<h3>问题定义</h3>

<p>先定义一下用到的符号</p>

<p>空间中有许多工厂，也有许多客户，集合\(F\)表示工厂集合，集合\(C\)表示客户集合，y要求给每个客户选择一个工厂，一个工厂可以被多个客户所选择，若一个工厂\(x\)被客户\(y\)所选择了，那么称\(y\)规\(x\)管理，定义距离函数为\(d(x,y)，x \in F, y\in C\)表示\(y\)选择\(x\)的代价。</p>

<p>具体问题是找到最多\(k\)个工厂，管理所有的客户，使得距离函数和最小。</p>

<p>这个问题在公制空间上的版本成为Metric K-median问题，是指\(d(x,y)\)满足正定性，对称性和三角形不等式。</p>

<h3>NP？</h3>

<p>这其实并不是一个NP-Hard问题，设计近似算法的原因在于加速运算</p>

<p>\(C_{2n}^{n}\)依旧是多项式复杂度内的问题。</p>

<h3>局部搜索算法</h3>

<p>首先可以通过简单分析得到选\(k\)个工厂一定比选择小于\(k\)个工厂要优。</p>

<p>现在来介绍一种简单的近似算法。</p>

<p>首先随机选择一个集合\(S\), 使得\(S \subset F\)， 并且\(|S| = k\)， 为了描述方便，扩展一下距离函数的定义令\(d(S,y) = \min{d(x,y)},x\in S, y\in C\)</p>

<p>然后枚举每个不在\(S\)中的工厂\(z\), 尝试替换\(S\)中的工厂\(x\), 如果能使得答案变得更优就换掉。</p>

<p>这样就会得到一个局部最优解。</p>

<p>实现思路非常简单而且是多项式时间复杂度的做法。</p>

<h3>近似度分析</h3>

<p>令最优解所选择的工厂集合为\(S^{*}\), 其中的元素一般使用\(o\)来表示。</p>

<p>令上面算法得到的工厂集合为\(S\), 其中的元素一般使用\(s\)来表示。</p>

<p>令\(C(x)，x\in F\)表示\(x\)这个元素管理的客户的集合。</p>

<p>首先定义一个术语叫做**捕获**，如果\(C(s) \bigcap C(o) \geq \frac{1}{2}C(o)\)则称\(s\)捕获了\(o\)。</p>

<h4>引理</h4>

<p>如果\(C(s) \bigcap C(o) &lt; \frac{1}{2}C(o)\)，则\(C(o)\)存在一个自己到自己的满射，使得每一个\(x \in C(s)\bigcap C(o)\)，可以映射到\(C(o) - C(s)\).</p>

<p><del>我也不知道为什么</del></p>

<h4>定理</h4>

<p>该局部搜索算法的近似度为5</p>

<h4>证明</h4>

<p>首先将\(S\)根据捕获的最优解中元素的个数分类</p>

<ul>
<li><p>\(S_{0}\)集合表示每个元素不捕获任何最优解中的元素</p></li>
<li><p>\(S_{1}\)集合表示每个元素都捕获最优解中的一个元素</p></li>
<li><p>\(S_{2}\)集合表示每个元素都捕获最优解中的至少两个元素</p></li>
</ul>

<p>下面进行\(k\)次交换，注意并不是连续进行\(k\)次交换，而是每次都从初始状态进行交换，综合考虑其的代价。</p>

<p>考虑\(s \in S_{1}\)它所捕获的元素为\(o\)对于\(C(o) \bigcap C(s)\)的元素分配给\(o\)，更严格地这里将\(C(o)\)的所有元素全部分配\(o\)(这样相较于之前那种方式并不一定使得当前的答案更加优)，对于\(C(o)-C(s)\)的元素，因为其中的有个元素为\(y\)，假设在\(S^{*}\)中分配给了\(o^{*}\),由于\(s\)已经捕获了\(o\)并且因为\(s \in S_{1}\)于是\(o^{*}\)一定不被\(s\)所捕获，于是在\(C(o^{*})\)存在一个单射，假设\(s^{‘}\)为其的像，同时\(s^{’} \in C(s^{*})\) ,于是将\(s\)分配给\(s^{*}\)</p>

<p>由三角不等式\[d(y, s^{*}) \leq d(y,o^{*})+d(o^{*},s^{&#39;}) + d(s^{&#39;}, s^{*})\]</p>

<p>这样一次交换之后\(Cost\)的变化为</p>

<p>\(0 \leq Cost(S-s+o) - Cost(S) \leq \sum_{x \in C(o)} [d(o,x) - d(s,x)] + \sum_{x \in C(s) - C(o)}[d(y,o^{*})+d(o^{*},s^{&#39;}) + d(s^{&#39;}, s^{*}) - d(s, x)]\)</p>

<p>接下来考虑剩下的元素该如何交换，可以发现\(S_{0}\)中的每个元素最多使用\(2\)次便可以完成最优解中的每个元素被交换一次。</p>

<p>同时可以发现也满足以上不等式。</p>

<p>于是。</p>

<p>将这个不等式累加\(k\)次，得到\(0 \leq Cost(OPT) - Cost(S) + 2*(Cost(OPT) + Cost(OPT) + Cost(S) - Cost(S))\)</p>

<p>于是近似度为\(5\).</p>


    </div>
    <script>
      hljs.initHighlightingOnLoad()
    </script>
  <script src="https://cdnjs.cloudflare.com/ajax/libs/highlightjs-line-numbers.js/2.5.0/highlightjs-line-numbers.min.js"></script>
  <script>
      hljs.initHighlightingOnLoad();
      hljs.initLineNumbersOnLoad();
  </script>
  </body>
</html>